270 - Lining Up/arcila.cpp

   1 #include<sstream>
   2 #include<iostream>
   3 #include<stdio.h>
   4 #include<math.h>
   5 #include<algorithm>
   6 #include<vector>
   7 #include<map>
   8 #include<string>
   9 #define MAX(a,b) a>b?a:b
  10 #define toPAngle(angle) angle>0?angle:(angle+pi)
  11 #define D(X) cerr<<__LINE__<<" "<<#X<<" "<<x<<endl
  12 const double pi=acos(-1);
  13 using namespace std;
  14
  15 struct point{
  16   double x,y;
  17   point(){}
  18   point(string a){
  19     stringstream t(a);
  20     t>>x>>y;
  21     //    D(x),D(y);
  22   }
  23   bool operator <(const point &t)const{
  24     return x<t.x||(x==t.x &&y<t.y);
  25   }
  26 };
  27 int main(){
  28   int cases;
  29   scanf("%d",&cases);
  30   string aux;
  31   getline(cin,aux);
  32   getline(cin,aux);
  33   for(int ans;cases-- && cin.peek()!=EOF;printf("%d\n",ans),cases<=0?:printf("\n")){
  34     vector<point> p;
  35     ans=2;
  36     for(string dum;getline(cin,dum) && dum!="";p.push_back(point(dum)));
  37     if(p.size()<3)continue;
  38     sort(p.begin(),p.end());
  39     double m;
  40     for(int i=0;i<p.size()-1;++i){
  41       map<double,int> angles;
  42       for(int j=i+1;j<p.size();++j){
  43         m=toPAngle(atan2(p[i].y-p[j].y,p[i].x-p[j].x));
  44         if(angles.count(m))
  45           ++angles[m];
  46         else
  47           angles[m]=2;
  48         printf("%lf between (%lf, %lf) and (%lf, %lf), angles[m] = %d\n", m, p[i].x, p[i].y,
  49                p[j].x, p[j].y, angles[m]);
  50         ans=MAX(angles[m],ans);
  51       }
  52     }
  53   }
  54   return 0;
  55 }